#ifndef KD_H_
#define KD_H_

#include "stdafx.h"
#include "bvh.h"

class KD : public BVH
{
	struct Node
	{
		enum {LEAF_FLAG_BIT = sizeof(size_t) * 8 - 1};

		int dimension;		//dimension in which the split occured
		float splitPos;		//position where to find the split plane
		size_t dataIndex;

		bool isLeaf() const
		{
			const size_t NODE_TYPE_MASK = ((size_t)1 << LEAF_FLAG_BIT);
			return (dataIndex & NODE_TYPE_MASK) != 0;
		}

		size_t getLeftChildOrLeaf() const
		{
			const size_t INDEX_MASK = ((size_t)1 << LEAF_FLAG_BIT) - 1;
			return dataIndex & INDEX_MASK;
		}

		////constructor for inner nodes
		//Node(int dim, float split)
		//{
		//	dimension = dim;
		//	splitPos = split;
		//}
		////constructor for leafes
		//Node()
		//{
		//	dimension = -1;
		//	splitPos = FLT_MAX;
		//}
	};

	struct Plane 
	{
		float4 equation;

		Plane(Point _origin, Vector _normal) 
		{
			equation = _normal;
			equation.w = -equation.dot(_origin);
		}

		virtual float intersect(const Ray& _ray ) const
		{
			float ret=-1;

			float div = float4(_ray.d).dot(equation);
			if(fabs(div) >0.00001)
			{
				float dist = -float4(_ray.o).dot(equation) / div;
				ret = dist;
			}

			return ret;
		}
	};

	struct SplitRet
	{
		std::vector<Primitive*> left;
		std::vector<Primitive*> right;
	};
		
	std::vector<Node> m_nodes;
	std::vector<Primitive*> m_leafData;

	BBox scene;

public:

	//Builds the hierarchy over a set of bounded primitives
	void build(const std::vector<Primitive*> &_objects);

	//Intersects a ray with the BVH.
	IntersectionReturn intersect(const Ray &_ray, float _previousBestDistance) const;

	BBox getSceneBBox() const { return scene; };

	SplitRet splitPrimitive(Primitive* prim, Point _origin, Vector _normal, int dim);

};

#endif

